//
// Created by Lenovo on 2025/11/23.
//
#include <cstring>
#include "Kruskal.h"

void initEdgeSet(MGraph *graph, EdgeSet *edge) {
    int k = 0;
    for (int i = 0; i < graph->nodeNum; i++) {
        for (int j = i+1; j < graph->edgeNum; j++) {
            if (graph->edge[i][j]>0) {
                edge[k].begin = i;
                edge[k].end = j;
                edge[k].weight = graph->edge[i][j];
                k++;
            }
        }
    }
}

static int getRoot(int* uSet,int v) {
    while (v!=uSet[v]) {
        v=uSet[v];
    }
    return v;
}

int Kruskal(EdgeSet *edge, int num, int nodeNum, EdgeSet *result) {
    int* uSet = static_cast<int*>(malloc(num*sizeof(int)));
    if (!uSet) {
        return;
    }
    //初始化并查集
    for (int i = 0; i < num; i++) {
        uSet[i]=i;
    }
    result = static_cast<EdgeSet*>(malloc(sizeof(EdgeSet)*num));
    int count = 0,sum=0;
    for (int i = 0; i < num; i++) {
        int a =getRoot(uSet,edge[i].begin);
        int b=getRoot(uSet,edge[i].end);
        if (a!=b) {
            //不构成环
            uSet[a]=b;
            sum+=edge[i].weight;
            result[count].begin=edge[i].begin;
            result[count].end=edge[i].end;
            result[count].weight=edge[i].weight;
            count++;
        }
        if (count==nodeNum-1) {
            break;
        }
    }
    free(uSet);
    free(result);
    return sum;
}

void sortEdgeSet(EdgeSet *edge,int num) {
    EdgeSet* temp;
    for (int i = 0;i<num;i++) {
        for (int j = i+1;j<num;j++) {
            if (edge[j].weight > edge[i].weight) {
                memcpy(&temp,&edge[i],sizeof(EdgeSet));
                memcpy(&edge[i],&edge[j],sizeof(EdgeSet));
                memcpy(&edge[j],&temp,sizeof(EdgeSet));
            }
        }
    }
}
